#include <stdio.h>
int edge[10][10]={0};
int x[11]={0};
int dfs(int n,int v){
	int i;
	x[v]=1;
	printf("%d ",v);
	for(i=0;i<n;i++){
		if(x[i]==0 && edge[v][i]==1){
			dfs(n,i);
		}
	}
}
int bfs(int n,int v){
	int t[20],front=0,rear=1,i;
	t[0]=v;
	x[v]=1;
	while(front<rear){
		for(i=0;i<n;i++){
			if(x[i]==0 && edge[t[front]][i]==1){
				t[rear++]=i;
				x[i]=1;
			}
		}
		printf("%d ",t[front++]);
	}
}
int main(){
	int i,n,e;
	scanf("%d %d",&n,&e);
	for(i=0;i<e;i++){
		int v1,v2;
		scanf("%d %d",&v1,&v2);
		edge[v1][v2]=edge[v2][v1]=1;
	}
	for(i=0;i<n;i++){
		if(x[i]==0){
			printf("{ ");
			dfs(n,i);
			printf("}\n");
		}
	}
	for(i=0;i<n;i++){
		x[i]=0;
	}
	for(i=0;i<n;i++){
		if(x[i]==0){
			printf("{ ");
			bfs(n,i);
			printf("}\n");
		}
	}
} 

